package 链表;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-09-26
 **/

public class No138复制带随机指针的链表 {

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    private Map<Node, Node> map = new HashMap<>();

    // 深拷贝链表
    public Node copyRandomList(Node head) {

        Node dump = new Node(-1);
        Node last = dump;
        Node cur = head;

        while (cur != null) {

            Node newNode = new Node(cur.val);
            last.next = newNode;
            map.put(cur, newNode);
            last = newNode;
            cur = cur.next;

        }

        Node copyNode = dump.next;
        cur = head;
        while (cur != null) {

            copyNode.random = map.get(cur.random);
            cur = cur.next;
            copyNode = copyNode.next;

        }

        return dump.next;
    }

}
